package leetcode;

/*
459. 重复的子字符串
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
输入: "aba"
输出: False
示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
*/

public class problems_459 {
    public static void main(String[] args) {
        System.out.println(new Solution().repeatedSubstringPattern("abab"));
    }
    static class Solution {
        public boolean repeatedSubstringPattern(String s) {
            if (null == s) return false;
            if (s.length() == 1) return false;
            // 遍历
            for (int i = 1; i <= s.length() /2; i++) {
                // 只有整除才行
                if(s.length() % i != 0) continue;
                int divisor = s.length() / i;
                boolean check = true;
                for (int j = 1; j < divisor; j++) {
                    if (!checkSub(s,i,j)) {
                        check = false;
                        break;
                    }
                }
                if(check) return check;
            }
            return false;
        }
        // 判断子字符串是否成立
        private boolean checkSub(String s, int subLength, int index){
            // 字符串比较判断
            for (int i = 0; i < subLength; i++) {
                if(s.charAt(i) != s.charAt(index * subLength + i)){
                    return false;
                }
            }
            return true;
        }
    }
}